package org.example.code.test2025.one_month;

import java.util.List;

public class Solution {
    // 定义二叉树节点
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    // 主方法：根据排序好的 List 创建二叉搜索树
    public TreeNode sortedListToBST(List<Integer> nums) {
        // 调用辅助方法，传递整个列表
        return sortedListToBSTHelper(nums, 0, nums.size() - 1);
    }

    // 递归辅助方法，构建二叉搜索树
    private TreeNode sortedListToBSTHelper(List<Integer> nums, int left, int right) {
        if (left > right) {
            return null;  // 基本情况：如果范围无效，返回空节点
        }

        // 找到中间节点
        int mid = left + (right - left) / 2; // 避免溢出
        TreeNode root = new TreeNode(nums.get(mid));  // 创建当前根节点

        // 递归构建左子树和右子树
        root.left = sortedListToBSTHelper(nums, left, mid - 1);
        root.right = sortedListToBSTHelper(nums, mid + 1, right);

        return root;  // 返回构建的根节点
    }

    // 中序遍历打印二叉搜索树（验证结果）
    public void inorderTraversal(TreeNode root) {
        if (root != null) {
            inorderTraversal(root.left);  // 先遍历左子树
            System.out.print(root.val + " ");  // 打印根节点
            inorderTraversal(root.right);  // 再遍历右子树
        }
    }

    // 测试
    public static void main(String[] args) {
        Solution solution = new Solution();

        // 创建一个已排序的 List
        List<Integer> nums = List.of(-10, -3, 0, 5, 9);

        // 根据排序好的 List 创建二叉搜索树
        TreeNode root = solution.sortedListToBST(nums);

        // 输出构建的二叉搜索树的中序遍历
        System.out.print("Inorder Traversal of BST: ");
        solution.inorderTraversal(root);
        System.out.println();
    }
}
